package Hot100;

import java.util.Arrays;

/**
 * @author zhangmin
 * @create 2022-01-15 9:28
 */
public class findUnsortedSubarray581 {

    /**
     * 581. 最短无序连续子数组
     * 给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
     * 请你找出符合题意的 最短 子数组，并输出它的长度。
     * 1、用一个新的数组存排序后的数组，然后判断出现不同序列的长度
     * 2、从左到由记录遇到的最大值，则当前元素需要比前面的最大元素都大，从后向前需要当前元素比其后的最小元素都小
     * */
    public int findUnsortedSubarray1(int[] nums) {
        int[] sortNums=new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            sortNums[i]=nums[i];
        }
        Arrays.sort(sortNums);
        int i = 0;
        for (; i < nums.length; i++) {
            if (sortNums[i]!=nums[i]){
                break;
            }
        }
        int start=i;
        i=nums.length-1;
        for (; i >=0 ; i--) {
            if (sortNums[i]!=nums[i])
                break;
        }
        return start>i?0:i-start+1;
    }
    public int findUnsortedSubarray(int[] nums) {
        int n=nums.length;
        int maxn=Integer.MIN_VALUE,right=-1,minn=Integer.MAX_VALUE,left=-1;
        for (int i = 0; i < n; i++) {
            if (maxn>nums[i]){
                right=i;
            }else {
                maxn=nums[i];
            }
            if (minn<nums[n-i-1]){
                left=n-i-1;
            }else {
                minn=nums[n-i-1];
            }
        }
        return right==-1?0:right-left+1;
    }
    public static void main(String[] args) {
        findUnsortedSubarray581 obj=new findUnsortedSubarray581();
        int[] nums={2,6,4,8,10,9,15};
        System.out.println(obj.findUnsortedSubarray(nums));
    }
}
